package AlgorithmOJ;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 34255
 * Date: 2024-10-09
 * Time: 21:49
 */
public class answerKey {
    //704.二分查找
    public static int search(int[] nums, int target) {
        //定义循环不变量：区间[ )
        int left = 0;
        int right = nums.length;
        while(left < right){//区间为[ ),如果right==left,则区间不合法
            int middle = (left + right) / 2;
            if(nums[middle] > target){//更新right指针，已将排除掉middle位置，因为区间为[ )，右边界不包含right位置，所以让right=middle
                right = middle;
            }else if(nums[middle] < target){//更新left指针，现已排除掉middle位置,以为区间为[ ),左边界为有效位置，所以让left=middle+1
                left = middle + 1;
            }else{
                return middle;
            }
        }
        
        return -1;
    }

    //搜索插入位置
    public static int searchInsert(int[] nums, int target) {
        //定义循环不变量：区间[ )
        int left = 0;
        int right = nums.length;
        int middle = 0;
        while(left < right){//区间为[ ),如果right==left,则区间不合法
            middle = (left + right) / 2;
            if(nums[middle] > target){//更新right指针，已将排除掉middle位置，因为区间为[ )，右边界不包含right位置，所以让right=middle
                right = middle;
            }else if(nums[middle] < target){//更新left指针，现已排除掉middle位置,以为区间为[ ),左边界为有效位置，所以让left=middle+1
                left = middle + 1;
            }else{
                return middle;
            }
        }
        return left;
    }

    /**
     *
     * @param nums 数组
     * @param target 目标值
     * @return 返回对应下标
     */
    public static int findRightMargin(int[] nums,int target){
        //循环不变量：区间左闭右开
        int left = 0;
        int right = nums.length;
        while(left < right){//left == right 不符合区间定义
            int mid = left + (right - left) >>> 1;
            if(nums[mid] <= target){//nums[mid] == target,
                left = mid + 1;
            }else if(nums[mid] > target){
                right= mid;
            }
        }
        return left - 1;
    }

    public static int findLeftMargin(int[] nums,int target){
        //循环不变量：区间左闭右开

        int left = 0;
        int right = nums.length;
        while(left < right){
            int mid = left + (right - left) >>> 1;
            if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return left;
    }

    //34.在排序数组中查找元素的第一个和最后一个位置
    public static int[] searchRange(int[] nums, int target) {
        int start = findLeftMargin(nums,target);
        if(start == nums.length || nums[start] != target) return new int[]{-1,-1};
        int end = findRightMargin(nums,target);
        return new int[]{start,end};
    }

    //X的平方根
    public static int mySqrt(int x) {
        //定义区间不变量:左闭右开
        int left = 0;
        int right = 46341;//防止超过平方值超过int整数最大值
        while(left < right){
            int mid = (left + right) >>> 1;
            int ret = mid * mid;
            if(ret < x){//ret < 8,由于数组递增性质，mid 左边的元素无需再进行判断且遵循循环不变量，所以更新left = mid + 1
                left = mid + 1;
            }else if(ret > x){//ret > 8,由于数组递增性质，mid 右边的元素无需再进行判断，且遵循循环不变量，所以更新righr=mid
                right = mid;
            }else{
                return mid;
            }
        }
        return left - 1;//发现没有元素的平方值 == X，返回 left - 1,即X平方根的整数部位
    }

    //有效的完全平方数
    public boolean isPerfectSquare(int x) {
            //定义区间不变量:左闭右开
            int left = 0;
            int right = 46341;//防止超过平方值超过int整数最大值
            while(left < right){
                int mid = (left + right) >>> 1;
                int ret = mid * mid;
                if(ret < x){//ret < 8,由于数组递增性质，mid 左边的元素无需再进行判断且遵循循环不变量，所以更新left = mid + 1
                    left = mid + 1;
                }else if(ret > x){//ret > 8,由于数组递增性质，mid 右边的元素无需再进行判断，且遵循循环不变量，所以更新righr=mid
                    right = mid;
                }else{
                    return true;
                }
            }
            return false;//发现没有元素的平方值 == X，返回 false
        }

    public static void main(String[] args) {
        int[] nums = {1,2,3,4};
        searchInsert(nums,0);
        search(nums,0);
        searchRange(nums,2);
        System.out.println(mySqrt(10));
    }
}
